package code.starivan.leetcode;

import java.util.HashSet;

/**
 * Created by Ivan on 2015/10/21.
 */
/*

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

        For example,
        Given [100, 4, 200, 1, 3, 2],
        The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

        Your algorithm should run in O(n) complexity.
*/

public class N128_LongestConsecutiveSequence {
    public static void  test(){
        System.out.println(new N128_LongestConsecutiveSequence().longestConsecutive(new int[]{5,100, 4, 200, 1, 3, 2}));
    }

    public int longestConsecutive(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }

        HashSet<Integer> hashSet=new HashSet<>();
        for(int i=0;i<nums.length;++i){
            hashSet.add(nums[i]);
        }

        int maxLength=0;
        for(int i=0;i<nums.length;++i){
            int tmpLen=1;
            int tmpNum=nums[i];
            while (hashSet.contains(++tmpNum)){
                hashSet.remove(tmpNum);
                tmpLen++;
            }

            tmpNum=nums[i];
            while (hashSet.contains(--tmpNum)){
                hashSet.remove(tmpNum);
                tmpLen++;
            }

            maxLength=Math.max(maxLength,tmpLen);
        }

        return maxLength;
    }
}
